In cases where deterioration detection of a catalyst, which is arranged in an exhaust passage of an internal combustion engine using natural gas as fuel, is carried out by the use of the oxygen storage capacity (OSC) of the catalyst, an O2 sensor for detecting the concentration of oxygen flowing out of the catalyst may take an incorrect value due to the reaction of unborn methane. Accordingly, there has been disclosed a technique of carrying out the detection of catalyst deterioration by changing a determination reference value for catalyst deterioration (for example, see a first patent document). Thus, in the first patent document, the detection of catalyst deterioration is intended to be carried out in an accurate manner.